package SortAlgorithm;

import LinkedList.ListNode;

/**
 * @author zxc
 * @date 2023/01/14 11:50
 **/

/**
 * 题目 ：排序链表
 * 题目详述 ：
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class SortList_Iteration {
    public static void main(String[] args) {
        // debug测试用例：
        int i = 4;
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        ListNode node3 = new ListNode(1);
        node2.next = node3;
        ListNode node4 = new ListNode(3);
        node3.next = node4;
        sortList(node1);
    }
    /**
     * 核心思想 ：即，使用迭代思想，使用归并排序来实现链表排序
     * 步骤 ：
     * （1）首先，重新定义一个node节点指向head节点，使用node节点遍历整个链表，获取到链表长度listLength；
     * （2）其次，定义一个虚拟头结点dummy,为了后面更简便地去构建合并排序后的链表；
     * （3）外层for循环（和数组归并算法的迭代思想一致），所代表的是，合并子链表的次数：logn;
     * 需要注意的是，外层for循环结束条件 ：即，当要去合并的子链表长度 >= 主链表长度；（合并子链表长度 ===》 2的n次方）
     * （4）内层for循环，所代表的是在当前子链表长度step下，将step长度的子链表 合并成长度为2*step长度的子链表；
     * 实现具体细节 ：
     * 1.首先，由于是使用dummy虚拟头结点所指向的链表，来进行链表排序操作，所以 cur = dummy.next; 同时tail = dummy;
     * 即，重新定义cur节点指向dummy虚拟头结点所指向的链表头结点；
     * 由于子链表merge合并操作是两两对应操作的，
     * 所以每次merge合并子链表后的链表都需要加入到dummy虚拟头结点所指向的链表，同时tail节点也需要指向前面已经排序好的链表尾节点；
     * 2.while(cur != null),即使用while循环实现子链表合并操作；（while循环结束条件 ：即，已经遍历完子链表）；
     * 3.divide(node , step)方法 ：即，以node节点为所截取子链表的头结点，同时step为子链表长度；将主链表划分成长度为step的子链表；
     * 4.merge(node1 , node2)方法 ：即，由于长度为step的子链表中节点都是排序好的，需要构建一个长度为2*step的新子链表，
     *                             合并长度为step的子链表，从而使得长度为2*step的新子链表中所有节点都是排序的；
     * （5）最后的返回值，为dummy.next；
     * （由于我们是对于dummy虚拟头结点所指向的链表进行排序，则将dummy虚拟头结点所指向的经过归并排序的链表返回即可）
     */
    public static ListNode sortList(ListNode head) {
        int listLength = 0;
        // 定义node节点，指向链表头结点head，为保证不会去改变链表头结点；
        ListNode node = head;
        // dummy节点，作用 ：使用dummy节点，来实现使用排序后的链表替换掉原先的链表；
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // while循环，统计链表长度（所消耗的时间复杂度：O（n））
        while(node != null){
            node = node.next;
            listLength++;
        }
        // 即，外层for循环代表了所要进行子链表合并的次数（一般次数为 ：logn）
        // step，即代表了所要去合并的子链表长度step（1，2，4，.....,2的n次方....）,直至所要合并的子链表长度step > length(原本链表最大长度)
        for(int step = 1 ; step < listLength ; step += step){
            // 内层for循环，需要实现将链表根据step进行划分子链表；同时根据2*step的长度，进行merge合并操作；
            // 即，内层循环代表了将step长度子链表合并（merge）成 2*step长度子链表的完整过程；
            ListNode cur = dummy.next;
            ListNode tail = dummy;
            while(cur != null){
                // 即，第一个划分出来的子链表头结点为cur；
                // 同时，cur节点所指向的是 奇数位所要进行合并操作的子链表头结点
                ListNode left = cur;
                // 即，第二个划分出来的子链表头结点为 left节点后第step个节点；
                ListNode right = divide(left , step);
                // cur节点指向后一个需要进行划分（divide）同时合并（merge）的子链表头结点；
                // 同时，也是方便下一次的合并操作；
                cur = divide(right , step);
                // 将合并后链表 添加到 新链表尾节点的next位置
                tail.next = merge(left , right);
                while (tail.next != null){
                    // tail节点后移至当前链表的尾节点
                    tail = tail.next;
                    System.out.println(tail.val);
                }
            }
        }
        return dummy.next;
    }
    // divide方法 ：即，以left节点为子链表的头结点，step为子链表长度，从主链表中截取出子链表;
    // 返回值 ：所截取子链表尾节点在主链表中的后一个节点;
    private static ListNode divide(ListNode node, int step) {
        // 一开始就进行step--，是为了保证step == 0时，正在遍历的节点为划分子链表的尾节点；
        step--;
        while(node != null && step > 0){
            node = node.next;
            step--;
        }
        if(node == null){
            return node;
        }
        else {
            ListNode nextNode = node.next;
            node.next = null;
            return nextNode;
        }
    }

    // merge方法，即创建新链表，来对于子链表中节点排序的结果进行合并存储;
    private static ListNode merge(ListNode head1, ListNode head2) {
        // 虚拟头结点，用来存储新创建的链表（新创建的链表，用来存储子链表合并后的结果）
        ListNode dummy = new ListNode(0);
        // 定义一个cur指向dummy虚拟头结点，用来保证虚拟头结点dummy的值不会在之后的合并过程中被修改
        // 即，cur节点，用于构建新链表；
        // （即，所插入的节点都是在cur.next;后同时将cur = cur.next;使得cur随时指向新构建链表的尾节点）
        ListNode cur = dummy;
        // 即，while循环的结束条件为 ：当其中的某个子链表被遍历结束，即退出循环
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                // head1节点后移
                head1 = head1.next;
            }
            else{
                cur.next = head2;
                //head2节点后移
                head2 = head2.next;
            }
            cur = cur.next;
        }
        // 在while循环结束后，由于子链表中所有元素都是顺序存放的，即只需要将未遍历完的子链表后续节点续接到新创建的链表之后即可
        cur.next = head1 != null ? head1 : head2;
        // 需要注意的是，所需要返回的值，未新构建的链表的头结点（而并不是虚拟头结点dummy）
        return dummy.next;
    }
    /**
     * 分析:
     * （1）时间复杂度 ：由于使用的是归并排序的迭代算法，即所需要的时间复杂度为O（nlogn）；
     * （2）空间复杂度 ：O（1）；
     */
}
